package offer_test_40;

import java.util.Queue;

import struct.BinaryTreeNode;
import struct.MyStack;

//输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
//从树的根节点开始往下一直到叶结点所经过的结点形成一条路径。
public class five_PathInTree {
	public static void main(String[] args) {
		BinaryTreeNode root1 = new BinaryTreeNode();
		BinaryTreeNode node1 = new BinaryTreeNode();
		BinaryTreeNode node2 = new BinaryTreeNode();
		BinaryTreeNode node3 = new BinaryTreeNode();
		BinaryTreeNode node4 = new BinaryTreeNode();
		root1.leftNode = node1;
		root1.rightNode = node2;
		node1.leftNode = node3;
		node1.rightNode = node4;
		root1.value = 10;
		node1.value = 5;
		node2.value = 12;
		node3.value = 4;
		node4.value = 7;
		MyStack stack = new MyStack(100);
		printPath(root1, 22, stack);
	}

	public static void printPath(BinaryTreeNode root, int num, MyStack stack) {
		if (root != null && root.value <= num) {
			stack.push(root.value);	
			if (num - root.value > 0) {
				if (root.leftNode != null) {
					printPath(root.leftNode, num - root.value, stack);
				}
				if (root.rightNode != null) {
					printPath(root.rightNode, num - root.value, stack);
				}
				stack.pop();
			} else if (num == root.value) {
				int node = (int) stack.pop();
				System.out.print(node + " ");
				if (!stack.isEmpty()) {
					stack.iterator();
				}
				System.out.println();
			} else {
				stack.pop();
			}
		}

	}

}
